package leetcode;

//沿对角线遍历
public class DiagonalTraverse {

	public static void main(String[] args) {
		DiagonalTraverse object = new DiagonalTraverse();
		int[][] matrix = {{1, 2, 3, 4}, { 10 ,11, 5, 6}, {7, 8, 9, 12}};
		object.findDiagonalOrder(matrix);
	}
	
	private final int[][] dir = {{-1, 1}, {1, -1}};
	
    public int[] findDiagonalOrder(int[][] matrix) {
        if(matrix == null || matrix.length <= 0){
        	return new int[]{};
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[] res = new int[m * n];
        
        int index = 0;
        int lastX = 0;
        int lastY = 0;
        
        res[0] = matrix[0][0];
        for(int i = 0; i < res.length; i++){
        	System.out.println(lastX + "  " + lastY);
        	res[i] = matrix[lastX][lastY];
        	if(index == 0){
//        		if(lastX + dir[index][0] == 0 || lastY + dir[index][1] == n){
        		if(lastX == 0 || lastY == n - 1){
        			index = index ^ 1;
        			if(lastY == n - 1){
        				lastX = lastX + 1;
        			}else{
        				lastY = lastY + 1;
        			}
        		}else{
        			lastX = lastX + dir[index][0];
        			lastY = lastY + dir[index][1];
        		}
        	}else{
//        		if(lastY + dir[index][1] == 0 || lastX + dir[index][0] == m){
        		if(lastY == 0 || lastX == m - 1){
        			index = index ^ 1;
        			if(lastX  == m - 1){
        				lastY = lastY + 1;
        			}else{
        				lastX = lastX + 1;
        			}
        		}else{
        			lastX = lastX + dir[index][0];
        			lastY = lastY + dir[index][1];
        		}
        	}
        }
        
        for(int i = 0; i < res.length; i++){
        	System.out.print(res[i] + " ");
        }
        System.out.println();
        return res;
    }
}
